package 排序.utils;

import java.util.Arrays;

import static 排序.utils.Example.*;

/**
 * @description:
 * @author: ywk
 * @date: 2020-06-14
 */
public class CountSort {
    public static void main(String[] args) {
        Integer[] A = {1, 4, 3, 4, 5};
        countSort(A);
        show(A);

    }
    /**
     * 计数排序
     * @param
     */
    private static void countSort(Integer[] data) {

        // 得到最大最小值
        Integer max = (Integer) getMax(data);
        Integer min = (Integer)  getMin(data);
        // 得到辅助数组来存储data数组每一元素出现的次数
        // data数组中每一个数和最小值的差是一定的，这一步有排序的作用
        int[] help = new int[max - min + 1];
        for (int i = 0; i < data.length; i++) {
            int mapPos = data[i] - min;
            help[mapPos]++;
        }
        // 查看help数组
        int k = 0;
        // 得到输出数组
        for (int i = 0; i < help.length; i++) {
            //根据help数组中存的次数去取排列好的元素
            while (help[i] != 0) {
                data[k++] = min + i;
                help[i]--;
            }
        }
    }

}
